package com.south.base.test.arithmetic;

import org.junit.Assert;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author Administrator
 * @date 2020/6/11 14:27
 */
public class GreaterElement {
    /**
     * 给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
     * 找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
     * nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。
     * 如果不存在，对应位置输出 -1 。
     */
    @Test
    public void nextGreaterElement() {
        Assert.assertArrayEquals(new int[]{-1, 3, -1}, nextGreaterElement(new int[]{4, 1, 2}, new int[]{1, 3, 4, 2}));
        Assert.assertArrayEquals(new int[]{3, -1}, nextGreaterElement(new int[]{2, 4}, new int[]{1, 2, 3, 4}));
    }

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.empty() && nums2[i] > stack.peek())
                map.put(stack.pop(), nums2[i]);
            stack.push(nums2[i]);
        }
        while (!stack.empty())
            map.put(stack.pop(), -1);
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }

    /**
     * 给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），
     * 输出每个元素的下一个更大元素。
     * 数字 x 的下一个更大的元素是按数组遍历顺序，
     * 这个数字之后的第一个比它更大的数，
     * 这意味着你应该循环地搜索它的下一个更大的数。
     * 如果不存在，则输出 -1。
     */
    @Test
    public void nextGreaterElements2() {
        Assert.assertArrayEquals(new int[]{2, -1, 2}, nextGreaterElements2(new int[]{1, 2, 1}));
        Assert.assertArrayEquals(new int[]{3, 4, -1, 3, 3}, nextGreaterElements2(new int[]{1, 3, 4, 2, 1}));
    }

    public int[] nextGreaterElements2(int[] nums) {
        if (nums.length == 0) {
            return nums;
        }
        if (nums.length < 2) {
            return new int[]{-1};
        }
//        Stack<Integer> stack = new Stack<>();
        Stack<Integer> stackIndex = new Stack<>();
        int[] res = new int[nums.length];
        int max = nums[0], maxIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (max < nums[i]) {
                max = nums[i];
                maxIndex = i;
            }
        }
        for (int i = maxIndex + 1; i < nums.length; i++) {
            while (!stackIndex.empty() && nums[i] > nums[stackIndex.peek()]) {
                res[stackIndex.pop()] = nums[i];
            }
            stackIndex.push(i);
        }
        for (int i = 0; i <= maxIndex; i++) {
            while (!stackIndex.empty() && nums[i] > nums[stackIndex.peek()]) {
                res[stackIndex.pop()] = nums[i];
            }
            stackIndex.push(i);
        }
        while (!stackIndex.empty()) {
            res[stackIndex.pop()] = -1;
        }
        return res;
    }
}
